import java.util.*;
/**
 * 
 * 合并k个已排序的链表
 * 
 * 描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 
0
≤
n
≤
5000
0≤n≤5000，每个节点的val满足 
∣
v
a
l
∣
<
=
1000
∣val∣<=1000
要求：时间复杂度 
O
(
n
l
o
g
n
)
O(nlogn)
示例1

输入：
[{1,2,3},{4,5,6,7}]
复制
返回值：
{1,2,3,4,5,6,7}
复制
示例2

输入：
[{1,2},{1,4,5},{6}]
复制
返回值：
{1,1,2,4,5,6}
 * 
 */
public class 合并k个已排序的链表 {
    public static void main(String[] args) {
        
        // 第一个链表：1->4->5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);

        // 第二个链表：1->3->4
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        // 第三个链表：2->6
        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);

        ArrayList<ListNode> lists = new ArrayList<>();
        lists.add(l1);
        lists.add(l2);
        lists.add(l3);

        ListNode mergedList = mergeKLists(lists);

        System.err.println(mergedList.toString());

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    private static ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here

        if (lists == null || lists.isEmpty()) {
            return null;
        }
        return merge(lists, 0, lists.size() - 1);
    }


    private static ListNode merge(List<ListNode> lists, int l, int r) {
        if (l == r) {
            return lists.get(l);
        }
        if (l < r) {
            int mid = l + (r - l) / 2;
            ListNode left = merge(lists, l, mid);
            ListNode right = merge(lists, mid + 1, r);
            return mergeTwoLists(left, right);
        }
        return null;
    }

    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1!= null && l2!= null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if (l1!= null) {
            curr.next = l1;
        }
        if (l2!= null) {
            curr.next = l2;
        }
        return dummy.next;
    }

    private static class ListNode{

        public int val;
        public ListNode next;

        public ListNode(int val){

            this.val = val;
        }

        public String toString(){

            StringBuilder builder = new StringBuilder();

            builder.append(val);
            builder.append(",");

            ListNode nextNode = next;

            while(null!=nextNode){

                builder.append(nextNode.val);
                builder.append(",");
                nextNode = nextNode.next;
            }
            

            return builder.toString();
        }

    }
}
